[Chapter Nine][Previous]
[Next] [Art of
Assembly][Randall Hyde]
Art of Assembly: Chapter Nine
- 9.5 - Machine and Arithmetic Idioms
- 9.5.1 - Multiplying Without MUL and IMUL
- 9.5.2 - Division Without DIV and IDIV
- 9.5.3 - Using AND to Compute Remainders
- 9.5.4 - Implementing Modulo-n Counters
with AND
- 9.5.5 - Testing an Extended Precision
Value for 0FFFF..FFh
- 9.5.6 - TEST Operations
- 9.5.7 - Testing Signs with the XOR Instruction
9.5 Machine and Arithmetic Idioms
An idiom is an idiosyncrasy. Several arithmetic operations and 80x86
instructions have idiosyncracies that you can take advantage of when writing
assembly language code. Some people refer to the use of machine and arithmetic
idioms as "tricky programming" that you should always avoid in
well written programs. While it is wise to avoid tricks just for the sake
of tricks, many machine and arithmetic idioms are well-known and commonly
found in assembly language programs. Some of them can be really tricky,
but a good number of them are simply "tricks of the trade." This
text cannot even begin to present all of the idioms in common use today;
they are too numerous and the list is constantly changing. Nevertheless,
there are some very important idioms that you will see all the time, so
it makes sense to discuss those.
9.5.1 Multiplying Without MUL and IMUL
If you take a quick look at the timing for the multiply instruction,
you'll notice that the execution time for this instruction is rather long.
Only the div and idiv instructions take longer
on the 8086. When multiplying by a constant, you can avoid the performance
penalty of the mul and imul instructions by using
shifts, additions, and subtractions to perform the multiplication.
Remember, a shl operation performs the same operation as multiplying
the specified operand by two. Shifting to the left two bit positions multiplies
the operand by four. Shifting to the left three bit positions multiplies
the operand by eight. In general, shifting an operand to the left n bits
multiplies it by 2n. Any value can be multiplied by some constant using
a series of shifts and adds or shifts and subtractions. For example, to
multiply the ax register by ten, you need only multiply it
by eight and then add in two times the original value. That is, 10*ax
= 8*ax + 2*ax. The code to accomplish this is
shl ax, 1 ;Multiply AX by two
mov bx, ax ;Save 2*AX for later
shl ax, 1 ;Multiply AX by four
shl ax, 1 ;Multiply AX by eight
add ax, bx ;Add in 2*AX to get 10*AX
The ax register (or just about any register, for that matter)
can be multiplied by most constant values much faster using shl than
by using the mul instruction. This may seem hard to believe
since it only takes two instructions to compute this product:
mov bx, 10
mul bx
However, if you look at the timings, the shift and add example above requires
fewer clock cycles on most processors in the 80x86 family than the mul
instruction. Of course, the code is somewhat larger (by a few bytes),
but the performance improvement is usually worth it. Of course, on the later
80x86 processors, the mul instruction is quite a bit faster
than the earlier processors, but the shift and add scheme is generally faster
on these processors as well.
You can also use subtraction with shifts to perform a multiplication operation.
Consider the following multiplication by seven:
mov bx, ax ;Save AX*1
shl ax, 1 ;AX := AX*2
shl ax, 1 ;AX := AX*4
shl ax, 1 ;AX := AX*8
sub ax, bx ;AX := AX*7
This follows directly from the fact that ax*7 = (ax*8)-ax.
A common error made by beginning assembly language students is subtracting
or adding one or two rather than ax*1 or ax*2.
The following does not compute ax*7:
shl ax, 1
shl ax, 1
shl ax, 1
sub ax, 1
It computes (8*ax)-1, something entirely different (unless, of course, ax
= 1). Beware of this pitfall when using shifts, additions, and subtractions
to perform multiplication operations.
You can also use the lea instruction to compute certain products on 80386
and later processors. The trick is to use the 80386 scaled index mode. The
following examples demonstrate some simple cases:
lea eax, [ecx][ecx] ;EAX := ECX * 2
lea eax, [eax]eax*2] ;EAX := EAX * 3
lea eax, [eax*4] ;EAX := EAX * 4
lea eax, [ebx][ebx*4] ;EAX := EBX * 5
lea eax, [eax*8] ;EAX := EAX * 8
lea eax, [edx][edx*8] ;EAX := EDX * 9
9.5.2 Division Without DIV and IDIV
Much as the shl instruction can be used for simulating
a multiplication by some power of two, the shr and sar
instructions can be used to simulate a division by a power of two.
Unfortunately, you cannot use shifts, additions, and subtractions to perform
a division by an arbitrary constant as easily as you can use these instructions
to perform a multiplication operation.
Another way to perform division is to use the multiply instructions. You
can divide by some value by multiplying by its reciprocal. The multiply
instruction is marginally faster than the divide instruction; multiplying
by a reciprocal is almost always faster than division.
Now you're probably wondering "how does one multiply by a reciprocal
when the values we're dealing with are all integers?" The answer, of
course, is that we must cheat to do this. If you want to multiply by one
tenth, there is no way you can load the value 1/10th into an 80x86 register
prior to performing the division. However, we could multiply 1/10th by 10,
perform the multiplication, and then divide the result by ten to get the
final result. Of course, this wouldn't buy you anything at all, in fact
it would make things worse since you're now doing a multiplication by ten
as well as a division by ten. However, suppose you multiply 1/10th by 65,536
(6553), perform the multiplication, and then divide by 65,536. This would
still perform the correct operation and, as it turns out, if you set up
the problem correctly, you can get the division operation for free. Consider
the following code that divides ax by ten:
mov dx, 6554 ;Round (65,536/10)
mul dx
This code leaves ax/10 in the dx register.
To understand how this works, consider what happens when you multiply ax
by 65,536 (10000h). This simply moves ax into dx
and sets ax to zero. Multiplying by 6,554 (65,536 divided
by ten) puts ax divided by ten into the dx register.
Since mul is marginally faster than div , this
technique runs a little faster than using a straight division.
Multiplying by the reciprocal works well when you need to divide by a constant.
You could even use it to divide by a variable, but the overhead to compute
the reciprocal only pays off if you perform the division many, many times
(by the same value).
9.5.3 Using AND to Compute Remainders
The and instruction can be used to quickly compute remainders
of the form:
dest := dest MOD 2n
To compute a remainder using the and instruction, simply and
the operand with the value 2n-1. For example, to compute ax = ax mod
8 simply use the instruction:
and ax, 7
Additional examples:
and ax, 3 ;AX := AX mod 4
and ax, 0Fh ;AX := AX mod 16
and ax, 1Fh ;AX := AX mod 32
and ax, 3Fh ;AX := AX mod 64
and ax, 7Fh ;AX := AX mod 128
mov ah, 0 ;AX := AX mod 256
; (Same as ax and 0FFh)
9.5.4 Implementing Modulo-n Counters with AND
If you want to implement a counter variable that counts up to 2n-1 and
then resets to zero, simply using the following code:
inc CounterVar
and CounterVar, nBits
where nBits is a binary value containing n one bits right justified in the
number. For example, to create a counter that cycles between zero and fifteen,
you could use the following:
inc CounterVar
and CounterVar, 00001111b
9.5.5 Testing an Extended Precision Value for 0FFFF..FFh
The and instruction can be used to quickly check a multi-word
value to see if it contains ones in all its bit positions. Simply load the
first word into the ax register and then logically and the
ax register with all the remaining words in the data structure.
When the and operation is complete, the ax register will contain
0FFFFh if and only if all the words in that structure contained 0FFFFh.
E.g.,
mov ax, word ptr var
and ax, word ptr var+2
and ax, word ptr var+4
.
.
.
and ax, word ptr var+n
cmp ax, 0FFFFh
je Is0FFFFh
9.5.6 TEST Operations
Remember, the test instruction is an and instruction
that doesn't retain the results of the and operation (other than the flag
settings). Therefore, many of the comments concerning the and operation
(particularly with respect to the way it affects the flags) also hold for
the test instruction. However, since the test instruction
doesn't affect the destination operand, multiple bit tests may be performed
on the same value. Consider the following code:
test ax, 1
jnz Bit0
test ax, 2
jnz Bit1
test ax, 4
jnz Bit3
etc.
This code can be used to successively test each bit in the ax register
(or any other operand for that matter). Note that you cannot use the test/cmp
instruction pair to test for a specific value within a string of
bits (as you can with the and/cmp instructions). Since test
doesn't strip out any unwanted bits, the cmp instruction
would actually be comparing the original value rather than the stripped
value. For this reason, you'll normally use the test instruction
to see if a single bit is set or if one or more bits out of a group of bits
are set. Of course, if you have an 80386 or later processor, you can also
use the bt instruction to test individual bits in an operand.
Another important use of the test instruction is to efficiently
compare a register against zero. The following test instruction sets the
zero flag if and only if ax contains zero (anything anded with
itself produces its original value; this sets the zero flag only if that
value is zero):
test ax, ax
The test instruction is shorter than
cmp ax, 0
or
cmp eax, 0
though it is no better than
cmp al, 0
Note that you can use the and and or instructions
to test for zero in a fashion identical to test. However, on
pipelined processors like the 80486 and Pentium chips, the test instruction
is less likely to create a hazard since it does not store a result back
into its destination register.
9.5.7 Testing Signs with the XOR Instruction
Remember the pain associated with a multi-precision signed multiplication
operation? You need to determine the sign of the result, take the absolute
value of the operands, multiply them, and then adjust the sign of the result
as determined before the multiplication operation. The sign of the product
of two numbers is simply the exclusive-or of their signs before performing
the multiplication. Therefore, you can use the xor instruction
to determine the sign of the product of two extended precision numbers.
E.g.,
32x32 Multiply:
mov al, byte ptr Oprnd1+3
xor al, byte ptr Oprnd2+3
mov cl, al ;Save sign
; Do the multiplication here (don't forget to take the absolute
; value of the two operands before performing the multiply).
.
.
.
; Now fix the sign.
cmp cl, 0 ;Check sign bit
jns ResultIsPos
; Negate the product here.
.
.
.
ResultIsPos:
- 9.5 - Machine and Arithmetic
Idioms
- 9.5.1 - Multiplying Without MUL and IMUL
- 9.5.2 - Division Without DIV and IDIV
- 9.5.3 - Using AND to Compute Remainders
- 9.5.4 - Implementing Modulo-n Counters
with AND
- 9.5.5 - Testing an Extended Precision
Value for 0FFFF..FFh
- 9.5.6 - TEST Operations
- 9.5.7 - Testing Signs with the XOR Instruction
Art of Assembly: Chapter Nine - 27 SEP 1996
[Chapter Nine][Previous]
[Next] [Art of
Assembly][Randall Hyde]